#ifndef __HEAP
#define __HEAP

#ifdef __cplusplus
extern "C" {
#endif

typedef struct {
	int val;
	int stream_index;
} queue_element;

typedef struct {
	queue_element *q;
	int PQ_SIZE;
	int n;
} priority_queue;


int pq_parent(int n);
int pq_young_child(int n);
void pq_insert(priority_queue *q, queue_element x);
void bubble_up(priority_queue *q, int p);
void pq_init(priority_queue *q, int size);
void make_heap(priority_queue *q, queue_element s[], int n);
queue_element extract_min(priority_queue *q);
void bubble_down(priority_queue *q, int p);
void heapsort(queue_element s[], int n);
void pq_swap(priority_queue *q, int p, int parent);
int pq_is_empty(priority_queue *q);

#ifdef __cplusplus
}
#endif

#endif
